package com.gitee.feizns.explore.data_structure.linked_list.singly.nextLargerNodes;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author feizns
 * @since 2020/3/6
 */
public class NextLargerNodes {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new NextLargerNodes().nextLargerNodes(create())));
    }

    private static ListNode create() {
        ListNode ret = new ListNode(2);
        ret.next = new ListNode(1);
        ret.next.next = new ListNode(5);
        return ret;
    }

    public int[] nextLargerNodes(ListNode head) {
        helper(head, 0);
        return ret;
    }

    Stack<Integer> stack = new Stack<>();

    int[] ret;

    private void helper(ListNode node, int index) {
        if ( node == null )
            ret = new int[index];
        else {
            helper(node.next, index + 1);
            while ( !stack.isEmpty() ) {
                Integer peek = stack.peek();
                if ( node.val < peek ) {
                    ret[index] = peek;
                    stack.push(node.val);
                    return;
                } else
                    stack.pop();
            }
            stack.push(node.val);
        }
    }

}
